#leetcode题目68：文本左右对齐
#难度：困难

#方法：模拟

from typing import List
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def blank(n):
            return ' ' * n
        ans = []
        right = 0
        n = len(words)
        
        while True:
            left = right
            sumLen = 0
            
            # 确定当前行能放多少个单词
            while right < n and sumLen + len(words[right]) + right - left <= maxWidth:
                sumLen += len(words[right])
                right += 1
            
            # 如果是最后一行
            if right == n:
                s = " ".join(words[left:])
                ans.append(s + blank(maxWidth - len(s)))
                break
            
            numWords = right - left
            numSpaces = maxWidth - sumLen
            
            # 如果只有一个单词
            if numWords == 1:
                ans.append(words[left] + blank(numSpaces))
            else:
                # 多个单词，需要分配空格
                avgSpaces = numSpaces // (numWords - 1)
                extraSpaces = numSpaces % (numWords - 1)
                
                s1 = blank(avgSpaces + 1).join(words[left:left + extraSpaces + 1])
                s2 = blank(avgSpaces).join(words[left + extraSpaces + 1:right])
                ans.append(s1 + blank(avgSpaces) + s2)
        
        return ans




#测试数据
words=["This", "is", "an", "example", "of", "text", "justification."]
maxWidth=16
#预期输出：
# ["This    is    an",
# "example  of text",
# "justification.  "]
solution=Solution()
print(solution.fullJustify(words,maxWidth))